#include<iostream>
#include<math.h>
#include<fstream>

#include "stopwatch.cpp"


class Player
{
	public:
	int amount;  
	int ct;
	Player()
	{
		amount=0;
		ct=0;
	}
	int giveMoney()
	{
		if(amount==0) return -1; 
		int current=int(pow(2,ct));
		if(current>amount)
		{
			int temp=amount;
			amount=0;
			return temp;
		}
		else
		{
			amount=amount-current;
			ct++;
			return current; 
		}
	}
	int takeMoney(int money)
	{
		if(amount==0) return -1; 
		amount+=money; 
	}
};

struct PlayerLinkedList
{
	int id;
	Player p;
	PlayerLinkedList *next;
};

int getLinkedListCount(PlayerLinkedList *root)
{
	PlayerLinkedList *temp=root;
	int i=0;
	int startId=root->id;
	while(temp->next->id!=startId)
	{
		temp=temp->next;
		i++;
	}
	return i;
}

PlayerLinkedList* removeNode(PlayerLinkedList *root, PlayerLinkedList *node)
{
	PlayerLinkedList *temp=root;
	int startId=root->id;
	while(1)
	{
		if(temp->next->id==node->id)
		{
			temp->next=temp->next->next;
			break;
		}
		if(temp->next->id==startId)
			break;
		temp=temp->next;
	}
	return (PlayerLinkedList *)temp;
}

PlayerLinkedList* getNode(PlayerLinkedList *root, PlayerLinkedList *node)
{
	PlayerLinkedList *temp=root;
	int startId=root->id;
	while(1)
	{
		if(temp->next->id==node->id)
		{
			return (PlayerLinkedList *)temp->next;
			break;
		}
		if(temp->next->id==startId)
			break;
		temp=temp->next;
	}
	return NULL;

}

void printLinkedList(PlayerLinkedList *root)
{
	PlayerLinkedList *temp=root; 
	int startId=root->id;
	while(temp->next->id!=startId)
	{
		printf("\t\tPlayer %d with $%d \n",(temp->id+1),temp->p.amount);
		temp=temp->next;
	}
}

void playGameLinkedList(int no_of_player, int initial_amt,int gameCnt)
{	gameCnt++;
	printf("\nResult for Game:%d\n",gameCnt);
	printf("\t\t%d Player in this game, $%d per Player \n",no_of_player,initial_amt);
	//create the circular linked list
	PlayerLinkedList *pListRoot;
	pListRoot=new PlayerLinkedList;
	pListRoot->id=no_of_player-1;
	pListRoot->p.amount=initial_amt;
	pListRoot->next=NULL;
	PlayerLinkedList *pLastNode;
	pLastNode=pListRoot;
	for(int i=no_of_player-2;i>=0;i--)
	{
		PlayerLinkedList *node=new PlayerLinkedList;
		node->id=i;
		node->p.amount=initial_amt;
		node->next=pListRoot;
		pListRoot=node;
	}
	pLastNode->next=pListRoot;

	PlayerLinkedList *currentGiver=pListRoot;
	int exMon=0;
	int monLeft=0;

	while(getLinkedListCount(pListRoot)>0)
	{
		int _flag=0;
		PlayerLinkedList *playerTaking=currentGiver;
		//printf("\nCurrent Giver id : %d\t Amount : %d\n",currentGiver->id,currentGiver->p.amount);
		while(currentGiver->p.amount>0)
		{
			playerTaking=playerTaking->next;
			if(playerTaking->id==currentGiver->id)
			{
				_flag=1;
				break;
			}
			int amt=currentGiver->p.giveMoney();
			playerTaking->p.takeMoney(amt);
			exMon++;

			//printf("\tPlayer Taking Id : %d\t Taken Amount : %d\t Total Amount left : %d\n",playerTaking->id,amt,playerTaking->p.amount);
		}
		if(_flag) break;
		pListRoot=(PlayerLinkedList *)removeNode(pListRoot,currentGiver);
		currentGiver=(PlayerLinkedList *)getNode(pListRoot,playerTaking);			
	}
	printf("\t\t%d Total money exchanges\n",exMon);
	printf("\t\tLast Player to give money : Player %d with $%d remaining\n",(currentGiver->id+1),currentGiver->p.amount);
	printf("\tPlayer remaining:\n");

	printLinkedList(pListRoot);

}

int main()
{
	fstream file("PROJ1.DAT",ios::in);
	if(!file)
	{
		cout << "error reading file 1\n";
		return (1);
	}
	int rows=73;
	int cols=2;
	int **array;
	array = new int*[rows];
	for(int i=0; i<rows; i++)
	array[i] = new int [cols];
			for(int i=0; i<rows; i++)
			{
				for(int j=0; j<cols; j++)
					file >> array[i][j];
			}
			for(int i=0; i<rows; i++)
			{
				Stopwatch sw;
				sw.start();
				int gameCnt=0;
				playGameLinkedList(array[i][0],array[i][1],i);
				sw.stop();
				double timeTaken=sw.user();
				printf("Run Time : %lf\n",timeTaken);
			}

	return 0;
}
